public final class busqueda_local2 extends Ejercicio
{ 
	public int[] Vo1, Vo2;
	private int cruces;
	
	protected Resultado DGIB
	(
			int n1, int v1[], int n2, int v2[], int m, Eje v1v2[],
			int np1, int vp1[], int np2, int vp2[], int mp, Eje vp1vp2[]
	){
		Resultado res = new Resultado();

		int i, N1 = n1+np1, N2 = n2+np2, M = m+mp;
		Nodo[] V1 = new Nodo[N1], V2 = new Nodo[N2];
		Eje[] V1V2 = new Eje[M];
		
		//4 declaraciones
		//3 declaraciones-asignaciones
		//3 operaciones basicas
		addPasos(10);
		
		for( i = 0; i < n1; i++ )
			V1[i] = new Nodo(v1[i],false);
		
		for( i = 0; i < np1; i++ )
			V1[i + n1] = new Nodo(vp1[i],true);
		
		for( i = 0; i < n2; i++ )
			V2[i] = new Nodo(v2[i],false);
		
		for( i = 0; i < np2; i++ )
			V2[i + n2] = new Nodo(vp2[i],true);
		
		for( i = 0; i < m; i++ )
			V1V2[i] = v1v2[i];
		
		for( i = 0; i < mp; i++ )
			V1V2[m+i] = vp1vp2[i];
		
		//n1 comparaciones
		//n1 operaciones basicas
		//n1 declaraciones-asignaciones
		//np1 comparaciones
		//np1*2 operaciones basicas
		//np1 declaraciones-asignaciones
		//n2 comparaciones
		//n2 operaciones basicas
		//n2 declaraciones-asignaciones
		//np2 comparaciones
		//np2*2 operaciones basicas
		//np2 declaraciones-asignaciones
		//m comparaciones
		//m operaciones basicas
		//m declaraciones-asignaciones
		//mp comparaciones
		//mp*2 operaciones basicas
		//mp comparaciones
		//mp declaraciones-asignaciones
		addPasos( n1*3+np1*4+n2*3+np2*4+m*3+mp*4 );
		
		Hconstructiva constructiva = new Hconstructiva();
		constructiva.DGIB(n1, v1, n2, v2, m, v1v2, np1, vp1, np2, vp2, mp, vp1vp2);
		
		//1 declaracion-asignacion
		//1 llamada a funcion
		//pasos de constructiva
		addPasos( 2 + constructiva.getPasos() );
		
		for(i = 0; i < N1; i++)
		{
			V1[i].valor = constructiva.Vo1[i];
			if(esta(vp1,V1[i].valor))
			{
				V1[i].incremental = true;
			}
			else
			{
				V1[i].incremental = false;
			}
		}
		for(i = 0; i < N2; i++)
		{
			V2[i].valor = constructiva.Vo2[i];
			if(esta(vp2,V2[i].valor))
			{
				V2[i].incremental = true;
			}
			else
			{
				V2[i].incremental = false;
			}
		}
		
		//N1 veces:
			//1 comparacion
			//2 operaciones basicas
			//2 asignaciones
		//N2 veces:
			//1 comparacion
			//2 operaciones basicas
			//2 asignaciones
		//2 asignaciones
		//2 comparaciones
		addPasos((N1+N2)*5+4);

		this.cruces = constructiva.cruces;
		//solucion optima
		this.Vo1 = new int[N1];
		this.Vo2 = new int[N2];

		localSearch
		(
			V1, N1,
			V2, N2,
			V1V2, M
		);
		
		cruces = cantidadCruces(Vo1,N1,Vo2,N2,V1V2,M);
		
		res.kid = cruces;
		res.n_iv1 = N1;
		res.iv1 = Vo1; 
		res.n_iv2 = N2;
		res.iv2 = Vo2;		
		
		//6 asignaciones
		//2 declaraciones-asignaciones
		//2 llamadas a funciones
		addPasos(10);
		
		return res;
	}
	
	public void localSearch
	(
		Nodo[] IV1, int N1,
		Nodo[] IV2, int N2,
		Eje[] IV1V2, int M 
	)
	{
		int crucesmenos,pasos=0,cantcruces;
		int[] V1 = new int [N1], V2 = new int[N2];

		crucesmenos = Vecindad(IV1,N1,IV2,N2,IV1V2,M,false);
		cantcruces = cruces - crucesmenos;
		
		//2 declaraciones
		//3 declaraciones-asignaciones
		//2 asignaciones
		//1 operacion basica
		//1 llamada a funcion
		addPasos(9);
		
		while( (cantcruces < cruces) && (pasos < 4*(N1+N2)) )
		{
			cruces = cantcruces;
			crucesmenos = Vecindad(IV1,N1,IV2,N2,IV1V2,M,false);
			cantcruces = cruces - crucesmenos;
			pasos++;
			
			//2 comparaciones
			//5 operaciones basicas
			//3 asignaciones
			//1 llamada a funcion
			addPasos(11);
		}
		
		//despues del ciclo
			//2 comparaciones
			//3 operaciones basicas
		addPasos(5);

		for(int i = 0; i < N1; i++)
		{
			V1[i] = IV1[i].valor ;
		}
			
		for(int i = 0; i < N2; i++)
		{
			V2[i] = IV2[i].valor;
		}
			
		System.arraycopy(V1, 0,this.Vo1, 0, N1); 
		System.arraycopy(V2, 0,this.Vo2, 0, N2);
		
		//N1 veces
			//1 comparacion
			//1 operacion basica
			//1 asignacion
		//N2 veces
			//1 comparacion
			//1 operacion basica
			//1 asignacion
		//copia de arreglo de N1 posiciones
		//copia de arreglo de N2 posiciones
		addPasos((N1+N2)*4);
	}
	
	private int Vecindad
	(
			Nodo Vmovil[], int Nmovil,
			Nodo Vfijo[], int Nfijo,
			Eje V1V2[], int M,
			boolean invertir
	){
		int i = 0, k, l, n, c=0, best_i = 0, best_c = 0,aux=0,res=0;
		boolean encontreVecino = false;
		Nodo v;
		
		//7 declaraciones-asignaciones
		//4 declaraciones
		addPasos(11);
		
		while( i < Nmovil && !encontreVecino)
		{
			if(Vmovil[i].incremental)
			{
				v = Vmovil[i];
				best_i = i;
				k = 0;
				n = i;
				
				//4 asignaciones 
				addPasos(4);
				
				for(int j = 0; j < M; j++)
				{
					if( invertir )
					{
						if(V1V2[j].destino == v.valor)
						{
							best_c = best_c +CrucesDelEje(Vfijo, Nfijo, Vmovil, Nmovil, V1V2, M,V1V2[j]);
							aux = best_c;
						}
					}
					else
					{
						if(V1V2[j].origen == v.valor)
						{
							best_c = best_c + CrucesDelEje(Vmovil, Nmovil, Vfijo, Nfijo, V1V2, M,V1V2[j]);
							aux = best_c;
						}
					}
					
					//2 comparaciones
					//3 operaciones basicas
					//2 asignaciones;
					//1 llamadas a funciones
					addPasos(8);
				}
				
				//antes del ciclo
					//1 declaracion-asignacion
				//despues del ciclo
					//1 comparacion
				addPasos(2);
				
				while( k < Nmovil)//ubico a v,en donde genera menos cruces
				{	
					if(k == 0)
					{
						for( l = n; l > k; l-- )
						{
							swap(Vmovil, l,l-1);
							
							//1 comparacion
							//2 operaciones basicas
							//1 llamada a funcion
							addPasos(4);
						}
						
						//antes del ciclo
							//1 asignacion
						//despues del ciclo
							//1 comparacion
						addPasos(2);
					}
					else
					{
						swap(Vmovil,n,k);
						
						//1 llamada a funcion
						addPaso();
					}
					
					//1 comparacion
					addPaso();
					
					c = 0;
					for(int j = 0; j < M; j++)
					{
						if( invertir )
						{
							if(V1V2[j].destino == v.valor)
							{
								c = c + CrucesDelEje(Vfijo, Nfijo, Vmovil, Nmovil, V1V2, M,V1V2[j]);
							}
						}
						else
						{
							if(V1V2[j].origen == v.valor)
							{
								c = c + CrucesDelEje(Vmovil, Nmovil, Vfijo, Nfijo, V1V2, M,V1V2[j]);
							}
						}
						
						//2 comparaciones
						//2 operaciones basicas
						//1 llamada a funcion
						addPasos(5);
					}
					
					//antes del ciclo
						//1 asignacion
						//1 declaracion-asignacion
					//despues del ciclo
						//1 comparacion
					addPasos(3);
					
					if(c < best_c)
					{
						best_i = k;
						best_c = c;
						encontreVecino = true;
					}

					n = k;
					k++;
					if(best_i <= i)
					{
						i++;
						
						//1 operacion basica
						addPaso();
					}
					
					//3 comparaciones
					//4 asignaciones
					//1 operacion basica
					addPasos(8);
				}
				
				//despues del ciclo
					//1 comparacion
				addPaso();
				
				for( l = n; l > best_i; l-- )
				{
					swap(Vmovil, l,l-1);
					
					//1 comparacion
					//2 operaciones basicas
					//1 llamada a funcion
					addPasos(4);
				}
				
				//antes del ciclo
					//1 asignacion
				//despues del ciclo
					//1 comparacion
				addPasos(2);
			}
			else
			{
				i++;
				
				//1 operacion basica
				addPaso();
			}
			
			//1 comparacion
			//3 operaciones basicas
			addPasos(4);
		}
		
		//despues del ciclo
			//1 comparacion
			//2 operaciones basicas
		addPasos(3);

		if( i >= Nmovil && !invertir)
		{
			res = Vecindad(Vfijo,Nfijo,Vmovil,Nmovil,V1V2,M,true);
			
			//1 asignacion
			//1 llamada a funcion
			addPasos(2);
		}
		else if(i < Nmovil)
		{
			res =(aux - best_c);
			
			//1 asignacion
			//1 operacion basica
			addPasos(2);
		}
		
		//2 comparaciones
		//2 operaciones basicas
		addPasos(4);
		
		return res;
	}
}